package practice_2025_9.practice_9_3;

class Solution {
    /**
     * 最大正方形
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        // 找到只包含 1 的最大正方形 -> 返回最大面积
        // dp[i][j]: [0, i], [0, j] 区间内的最大正方形面积(×)
        // dp[i][j]: [0, i], [0, j] 区间内, 以 [i, j] 结尾的最大正方形边长
        // m[i][j] = 0 -> 0
        // m[i][j] = 1 -> 找可能的最大正方形
        // 右下固定([i, j]) -> 右上( dp[i][j - 1] + 1) 左下(dp[i - 1][j] + 1) 左上(dp[i - 1][j - 1])
        // 需要同时满足
        // -> min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        // 初始化 -0
        // 填表
        int max = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    max = Math.max(dp[i][j], max);
                }
            }
        }
        return max * max;
    }

    /**
     * 最大二叉树
     * @param nums
     * @return
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        // 不重复整数数组 nums, 最大二叉树:
        // 根节点, 值为最大值
        // 递归在最大值左边创建左子树
        // 递归在最大值右边创建右子树

        // 找到最大值, 创建节点, 递归创建
        return construct(nums, 0, nums.length - 1);
    }
    public TreeNode construct(int[] nums, int begin, int end) {
        if (begin > end) {
            return null;
        } else if (begin == end) {
            return new TreeNode(nums[begin]);
        }
        // 找到区间内的最大值
        int max = nums[begin];
        int index = begin;
        for(int i = begin + 1; i <= end; i++) {
            if (nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }
        TreeNode node = new TreeNode(max);
        node.left = construct(nums, begin, index - 1);
        node.right = construct(nums, index + 1, end);
        return node;
    }
}

 class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
 }